面试经验分享之数据结构、算法题

1、两棵树相加——对应位置两棵树都有值则相加，对应位置只有一棵树有值则取该值；

2、用速度不同的指针可以判断链表中是否有环，问两速度满足怎样的关系可以保证发现环；

3、如何在语料中寻找频繁出现的字串，分析复杂度（tire树）；

4、中缀表达式转逆波兰表达式，逆波兰表达式求值；

5、数据解压缩，3(a4(ab)) -> aababababaababababaabababab；

6、二叉树的文件存储。

准备建议

上上之选当然是看《算法导论》，书 和 公开课 都算。时间精力不足又想临时抱佛脚，清华大学计算机系邓俊辉老师的 教材 是好选择，也可以看 公开课。注意熟记不同数据结构的不同操作的不同实现方式（比如 哈希表的插入删除查找）的复杂度分析，不管面试官给你出的题目是难是易，妥妥儿的会问复杂度。

算法题目

概述

有过面试经历的企业（BAT、小米、宜信、猿题库、FreeWheel等）当中，还没有谁问过我需要复杂算法（比方说 此链接 中的很多知识点）才能解决的问题。我遇到的算法题目大致可以分为两类：

●经典算法实现题 快速排序、归并排序、堆排序、KMP算法等都是重点，重要的是代码的正确性，其次是复杂度分析，当然，人家也不都是直接问你怎么实现这个具体算法，而是包装到情境里；

●思维益智题 考察你分析问题的能力，大部分可以归结到二分、动态规划、递归上，重要的是思路，其次是尽量低的复杂度，再次是代码的正确性。

下面具体介绍我遇到的两种类型题目中的问题。

分类讨论

类型一：经典算法实现题

1、实现快速排序、归并排序、堆排序，各排序算法复杂度分析；

2、实现KMP，解释原理；

3、迷宫的深度搜索、广度搜索；

4、写 find 函数，在目标串中匹配模式串（要考虑中文字符的情况）。

类型二：思维益智题

1、数列中找第 k 大的数字（与快排或堆排序有关）；

2、两个有序数组，寻找归并排序后数组的中位数/第 k 大数字（与二分有关）；

3、一维数组，swap 其中的几对数字（每个数字只属于一次 swap 操作），实现查找（与二分有关）；

4、一个有序数组，其中一个数字发生变异，但不知道变异后会不会影响整体序，如何实现查找；

5、二维数组，每行递增，每列递增

●实现查找；

●二维数组，每行递增，每列递增，求第 k 大的数；

●任意交换其中的两数，发现并恢复；

6、寻找字符串中第一个只出现一次的字符；

7、统计数列中的逆序对（归并排序有关）；

8、最长公共子串（动态规划有关）；

9、最大子序列和，允许交换一次的最大子序列和；

10、给定数组，寻找 next big（堆排序有关）；

11、一维有序数组，经过循环位移后，最小的数出现在数列中间

●如果原数组严格递增，如何找这个最小数；

●如果原数组严格递增或递减，如何找这个最小数；

●如果原数组非严格递增或递减，如何找这个最小数；

12、数组可能是递增、递减、递减后递增、递增后递减四种情况，递增递减都是非严格的，如果有转折点，返回转折点的值，否则返回-1；

13、单向网络，起点和终点唯一且连通，寻找那些一旦被删除将导致起点终点无法连通的点；

14、有序数组寻找和为某数的一对数字；

15、墙里能装多少水；

16、打印螺旋数组；

17、打印组合数；

18、字符数组，统计指定区间内的回文串个数。

准备建议

●不要纠结于是否是最佳思路，要保证能在 10-15 分钟内给出一个解决方案，并分析复杂度；

●基础的可以读读 @研究者July 的这本 电子书，更深入的可以阅读 CSDN 等博客中大牛们写的 ACM 解题报告；

●hihocoder、topcoder、leetcode、codility、POJ 等网站择一练手。

开放题目

这类开放题目让你自主选择数据结构，主要是考察求职者对于数据结构的特性与使用场景的综合理解，在面对具体应用场景时能否运用已有的数据结构和算法知识提出合理的解决方案。一般来说在这类问题里哈希表的出场率会比较高……例题如下

1、大数据量的 url log，怎么去重且统计每个 url 的出现次数，复杂度分析；

2、设计 cache 系统

●设计 cache 的接口；

●可以用什么数据结构实现；

●如何实现可伸缩的容量；

●cache 的空间管理策略，比如 cache 哪些条目，何时清理；

●cache 系统启动时分配多大的空间，之后按照怎样的策略增大；

3、设计爬虫；

4、流媒体播放客户端从多个完全相同的发送方接收视频包，同一发送方的包会按序到达，不同发送方的包则不一定，有可能会丢包，但还是要保证播放流畅度，设计播放客户端的算法。

总结

●数据结构和算法的基础知识还是十分重要的，大部分题目的思路来源于此；

●训练自己算法复杂度的分析能力，有的时候对复杂度的分析会反过来会帮助你找到更好的算法；

●一定量的题目积累很重要，就好像准备高考数学压轴题一样，见识的越多，思路来得越快，当然，前提是你能够不断总结反思。

来自：Blog of 太极儒

作者 Frank Song，微博@太极儒

来自：Blog of 太极儒

作者 Frank Song，微博@太极儒

---END---

推荐↓↓↓返回搜狐，查看更多